package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/8/17.<br><br>
 *
 * 中等：在排序数组中查找元素的第一个和最后一个位置
 */
public class Topic34 {

    public static void main(String[] args) {
        Topic34 instance = new Topic34();

        int[] array = new int[] {5,7,7,8,8,10};
        Util.printArray(instance.searchRange(array, 8));

        array = new int[] {5,7,7,8,8,10};
        Util.printArray(instance.searchRange(array, 6));

        array = new int[] {};
        Util.printArray(instance.searchRange(array, 0));
    }

    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums.length == 0) {
            return result;
        }

        helper(nums, 0, nums.length - 1, target, result);
        return result;
    }

    private void helper(int[] nums, int left, int right, int target, int[] result) {
        if(left > right) {
            return ;
        }

        int mild = (left + right) / 2;
        if(nums[mild] == target) {
            if(result[0] == -1) {
                result[0] = mild;
            }
            else {
                if(mild < result[0]) {
                    result[0] = mild;
                }
            }

            if(result[1] == -1) {
                result[1] = mild;
            }
            else {
                if(mild > result[1]) {
                    result[1] = mild;
                }
            }
        }

        helper(nums, left, mild - 1, target, result);
        helper(nums, mild + 1, right, target, result);
    }
}
